/*
#    if_contain_x64.c
#    SCHIPS
#    schips@dingtalk.com
#    https://gitee.com/schips/
#    Thu 27 Jun 2019 03:54:19 PM HKT
*/
#if 0
ref ：https://blog.csdn.net/m0_37846371/article/details/72854890
Rabin-Karp算法用来解决一个"简单"的问题: 
    在一个字符串中定位子串的位置.时间复杂度为O(m+n)

实现：
选取两个合适的互素常数b和h（l<b<h），假设字符串C=c1c2c3...cm，定义哈希函数：H(C)=（c1*b^(m-1)+c2*b^(m-2)+...+cm*b^0）mod h

其中b是基数，相当于把字符串看作b进制数。这样，字符串S=s1s2s3...sn从位置k+1开始长度为m的字符串子串S[k+1...k+m]的哈希值，就可以利用从位置k开始的字符串子串S[k...k+m-1]的哈希值，直接进行如下计算：H(S[k+1...k+m])=（H(S[k...k+m-1]）* b - sk*b^m + s(k+m)） mod h

于是，只要不断这样计算开始位置右移一位后的字符串子串的哈希值，就可以在O（n）时间内得到所有位置对应的哈希值，从而可以在O（n+m）时间内完成字符串匹配。

在实现时，可以用64位无符号整数计算哈希值，并取h等于2^64，通过自然溢出省去求模运算。
#endif 
#include <stdio.h>
#include <string.h>
typedef unsigned long long ull;
static const int false = -1;
static const int true = 0;
const ull b=100000007;//哈希的基数

//a是否在b中出现
int contain(const char* C,const char* S)
{
	int m,n;
    const char *c;
    const char *s;
    if(C == NULL || S == NULL)
    {
        return false;
    }
    c = C; s = S;
    m = strlen(c);
    n = strlen(s);
	if(m > n)
    {
        // 交换
        c = S;  s = C;
        m = m ^ n;
        n = m ^ n;
        m = m ^ n;
    }
	//计算b的m次方
	ull t=1;
    for(int i=0;i<m;i++){
		t*=b;
    }
	//计算C和S长度为m的前缀对应的哈希值
	ull Chash=0,Shash=0;

    for(int i=0;i<m;i++){
		Chash=Chash*b+c[i];
    }

	for(int i=0;i<m;i++)
    {
		Shash=Shash*b+s[i];
    }

	//对S不断右移一位，更新哈希值并判断
	for(int i=0;i+m<=n;i++)
	{
		if(Chash==Shash)
        {
			return true;
        }
		//S从位置i开始长度为m的字符串子串等于C；
		if(i+m<n)
        {
			Shash=Shash*b-s[i]*t+s[i+m];
        }
	}
	return false;
}
int main(int argc, char *argv[])
{
    int ret;
    ret = contain("gh", "asdfghk");
    printf("%d\n", ret);
    ret = contain("asdfghk", "gh");
    printf("%d\n", ret);
    return 0;
}
